#include <iostream>
using namespace std;


#include <queue>
#include <vector>

class Machine 
{
  public:
    int _starttime;
    int _worktime;

  public:
    int getsum() const
    {
      return _starttime + _worktime;
    }
  public:
    Machine() = default;

    Machine(int st , int wt)
      :_starttime(st)
       ,_worktime(wt)
    {}

    bool operator()(const Machine& obj1 , const Machine& obj2)
    {
      return obj1.getsum() > obj2.getsum();
    }
};



vector<int>  process0(vector<int>& arr , int num) 
{
  vector<int> ans;
  priority_queue<Machine , vector<Machine> , Machine> heap;

  for (auto x : arr)
  {
    heap.push(Machine(0 , x));
  }

  for (int i = 0; i < num; i++)
  {
    Machine cur  = heap.top();
    heap.pop();

    ans.push_back(cur.getsum());

    cur._starttime += cur._worktime;

    heap.push(Machine(cur._starttime , cur._worktime));
  }

  return ans;
}

// int -> min time 
// vector<int> drink time 
// a   
// b 
// abltime 
int process(vector<int>& end , int index , int a , int b , int avltime)
{
  if (index == static_cast<int>(end.size()))
  {
    return 0;
  }

  // possible 1 
  int p1 = max(a + end[index] , process(end , index+1 , a , b , avltime));

  // possible 2
  int p2 = max(b + end[index], process(end , index+1 , a , b , avltime + b));

  return min(p1 , p2);
}



int dpprocess(vector<int>& end , int a , int b , vector<vector<int>> dp)
{
  // dp[N][...] = 0;

  for (int indexdp = static_cast<int>(end.size()) - 1; indexdp >= 0 ; indexdp--)
  {
    for (int freetime = 0; freetime <= 10000 ; freetime++)
    {
      int p1 = max(a + end[indexdp] , dp[indexdp+1][freetime]);
      int p2 = max(b + end[indexdp] , dp[indexdp+1][freetime+b]);

      dp[indexdp][freetime] = min(p1 , p2);
    }
  }
  return dp[0][0];
}


int main()
{
  vector<int> arr = {1 , 3 , 7};
  vector<int> end = process0(arr , 7);

  int ret = process(end , 0 , 3 , 10 , 0);
  cout << ret << endl;

  cout << "dp -------------------------" << endl;

  vector<vector<int>> dp(15 , vector<int>(10001 , 0));
  cout << dpprocess(end , 3 , 10 , dp) << endl ; 
  return 0;
}
